/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
// 1. bfs层次遍历：最后一层为空时，返回上一层第一个节点
func findBottomLeftValue(root *TreeNode) int {
	var q []*TreeNode
	q = append(q, root)
	for len(q) > 0 {
		firstLastLevel := q[0]
		var tmp []*TreeNode
		for len(q) > 0 {
			n := q[0]
			q = q[1:]

			if n.Left != nil {
				tmp = append(tmp, n.Left)
			}
			if n.Right != nil {
				tmp = append(tmp, n.Right)
			}
		}

		if len(tmp) == 0 {
			return firstLastLevel.Val
		}
		q = tmp
	}

	return -1
}